import "sort"

/*
 * @lc app=leetcode.cn id=15 lang=golang
 *
 * [15] 三数之和
 */

// @lc code=start
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	res := [][]int{}
	for base := 0; base < len(nums)-2; base++ {
		if base > 0 && nums[base] == nums[base-1] {
			continue
		}
		low := base + 1
		high := len(nums) - 1
		sum := 0 - nums[base]
		for low < high {
			if nums[low]+nums[high] == sum {
				res = append(res, []int{nums[base], nums[low], nums[high]})
				for low < high && nums[low] == nums[low+1] {
					low++
				}
				for low < high && nums[high] == nums[high-1] {
					high--
				}
				low++ //nums是有序的 如果low++后还想维持nums[low]+nums[high] == sum,那么只有high--才有可能满足继续满足这一条件
				high--
			} else if nums[low]+nums[high] < sum {
				low++
			} else {
				high--
			}
		}
	}
	return res
}

// @lc code=end

